package com.linchong.binarysearch.easy;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-28 20:21
 * @Description: FirstBadVersion$
 * 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
 * 给定 n = 5，并且 version = 4 是第一个错误的版本。
 * <p>
 * 调用 isBadVersion(3) -> false
 * 调用 isBadVersion(5) -> true
 * 调用 isBadVersion(4) -> true
 * <p>
 * 所以，4 是第一个错误的版本。 
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/first-bad-version
 */
public class FirstBadVersion {
	boolean[] projects;
	boolean isBadVersion(int version) {
		return projects[version];
	}

	public int firstBadVersion(int n) {

		int start= 1;
		int end = n;
		while (start+1<end){
			int mid = start+(end-start)/2;
			if(isBadVersion(mid)){
				end = mid;
			}else{
				start=mid;
			}
		}

		if(isBadVersion(start)){
			return start;
		}

		if(isBadVersion(end)){
			return end;
		}

		return -1;

	}

	public static void main(String[] args) {
		FirstBadVersion instance = new FirstBadVersion();
		instance.projects = new boolean[]{false,false,false,false,true,true};
		System.out.println(instance.firstBadVersion(5));
	}


}

















